Subdivision of Kingdom

Memory limit: 32 MB

Byteasar, king of Byteotia, has finally decided to retire. He has two sons, however, and is unable to decide which one one of them should succeed him. Therefore he plans to split the kingdom into two halves, making each son a ruler.

After the division, watchtowers have to be built along the roads connecting the halves. Obviously, building them will be costly, so ideally there should be as little roads between the halves as possible.

Luckily, Byteotia consists of an even number of towns, connected by roads. Resulting from the division, each half-kingdom should contain half the towns. Each road connects (directly) two towns. The roads do not meet nor cross outside towns, though they can lead through flyovers or tunnels. Every two towns are directly connected by at most one road.

Which exact towns should lie in which half of the kingdom is a matter of great importance. You may assume that the land outside the towns can be partitioned in such a way that the roads connecting towns lying in the same half will not cross the border. On the other hand, one watchtower has to be built by each road connecting towns from different halves.

Task

Write a programme that:

• reads the descriptions of towns and the roads connecting them from the standard input,
• determines such a partition of kingdom into halves that both the halves contain an equal number of towns and the number of roads connecting towns lying in different halves is minimum,
• writes out the result to the standard output.

Input

The first line of the standard input contains two integers and , separated by a single space, denoting the number of towns and number of roads respectively, , , . The towns are numbered from to . Each of the following lines contains two integers separated by a single space. The line no. (for ) contains the numbers and , . These denote a road connecting and .

Output

Your programme should write out exactly one line to the standard output. It should contain integers separated by single spaces. These should be the numbers of towns belonging to the same half of the kingdom the town no. does, in an increasing order.

Example

For the input data:

6 8
1 2
1 6
2 3
2 5
2 6
3 4
4 5
5 6

the correct result is:

1 2 6

The dashed line in the figure shows the optimum partition, which requires building as little as watchtowers.

Task author: Zbigniew Czech.